923 332868
795627107 547135727 433141994 86388683 302728364 881453648 481936098 538699843 857998554 689585220 613263955 211227714 418290954 183501617 820193684 199989754 989353326 103080371 307606610 866110223 478221003 162270488 610152971 511199003 325968124 233736162 60864148 64405544 329843053 459337801 56358036 668955961 932061600 765955254 970408454 644138177 134008236 853315657 254298299 22364969 722753721 179282261 860197078 381116751 407848325 124038622 644206926 96004354 322412770 823988770 988277871 387283847 341651509 996433677 514523737 793436695 333729785 206824131 868470144 293869150 215147066 181353754 58027818 554207998 42475291 411225117 470746612 160007178 809633104 527912074 330889294 244575627 307425444 135549525 612598522 71581695 475541109 998200099 557661585 991233236 78009395 172085456 963182846 317969138 632522725 8608745 36060160 506570030 534155939 424436787 188998060 108698840 608149789 619326754 71611370 630239278 146203666 378540131 538483187 719208678 773069530 427504210 774169817 716645544 765420509 918199428 308695551 74141074 383668506 632366655 758029725 486446259 500913313 13892349 669824829 282824848 262156569 18426605 295949889 648090017 880056891 204890994 653181531 66097877 600369492 245512098 859394066 225668106 458907591 415233224 602448196 68758 562834313 484332770 333209502 97933761 726180772 293566243 918819622 866404680 154996916 913451634 50672306 239167964 87049581 379939306 100065902 583389089 854680339 41336152 37425754 915461807 402455552 801792960 587470026 200762261 290678817 862000601 105896676 879371217 203432313 782639756 633062693 768844889 865190046 366215544 587618269 943043605 82008375 388173169 226001326 252802146 403920516 615628541 75684369 448227728 468031958 31646422 8486353 765066085 40596754 49121387 653845901 171159961 998165810 758598750 876273722 905596504 967475396 658395399 258621855 701651139 726177897 819214063 683188952 565576559 585803607 464382294 288803540 47994084 412139992 272735919 624197335 955603487 494665161 288816926 861958905 693529360 818734876 582608641 429268132 13281565 759391830 810252644 48336153 482575261 640993041 533422219 795588588 164636254 582807163 302008428 571264388 65015840 964789206 348496690 410285980 618625816 772280566 925611452 69735365 861781358 365531846 140000795 593817570 724458943 638352835 950729751 281215658 170823067 273903231 297180587 78599209 274252808 644102175 626302853 241260607 131795453 700501214 209433991 90374431 448827112 321394824 310086473 399712210 501053737 502148863 607107220 125234866 833914004 979284666 18498024 10374639 107935475 355800385 818839287 314057741 933444738 621558194 374880552 199531108 490804849 449316159 958970389 92096415 841557350 57575342 452203021 51501118 647980536 581973464 413130387 703626004 673561909 999441962 675715292 50324425 9767709 323009319 552676437 691421016 466328356 337802723 121288476 982561938 356369076 608369802 8438402 409292954 799675817 137469143 152913295 642425192 214880979 513721501 226220414 932791366 927638647 42870850 92431932 758154837 349838543 646545215 6037741 53202185 600041093 97949857 669693032 416088745 966994236 792670603 216967606 563015376 423507975 285140402 12833430 614967023 489165808 439322079 9922044 786468552 986376819 664805489 22392462 807192308 92952576 605445592 374658854 977303903 453457532 383621403 306208595 741143495 338217920 365784147 678506967 980549184 312835609 462520110 930726698 899327410 499127494 484408685 157526518 703638617 106575486 158731622 986064793 344516677 723164647 249204866 517337254 156435416 576235552 169262016 299415396 751645259 830882616 249003057 162980941 379526184 787816628 380589946 133843088 589127633 539645965 25802837 704682640 153171960 990642480 380971280 529134179 567880229 444765436 87356940 328434772 810536756 193897415 325655615 483623778 555188180 360171482 731085234 894021055 860796681 638322672 301495300 161213265 511887530 421671355 546648294 206305332 841803235 604795487 671290525 132090165 293899189 98442485 12887172 342252633 88672625 774331146 132779399 734959956 23583553 210295581 35370664 484645395 282066079 198279972 576995197 55569715 764117212 345251079 374458032 987687559 648427418 463273764 270017150 918476181 851928402 123537610 584441145 20018202 963997648 543240894 226197446 15049346 809031346 940283833 407648800 67391600 106486252 673266407 712981459 2730300 337913926 921067113 537538177 297995376 657889244 269424084 592991329 560841803 1131677 891296432 368675515 523399230 797907662 188954875 568244845 249133425 495047044 797119395 130267241 590287167 423229229 390801679 759807028 49805749 810104840 503585687 765071977 959447575 682150568 426442247 225847604 160178524 685132917 1591329 109135576 843500717 16107562 800829207 481119274 665194474 335016024 87028757 630512915 507082277 833170914 575871157 97172753 903957540 119554175 361404296 589168054 591749347 994833724 11272852 80559912 242075664 375987447 638704593 953925280 421266062 688871141 795656619 483142379 771433202 988101388 572860291 11584236 783152649 338141898 648338990 71918104 92367184 952052556 287470708 234267896 214457722 66546712 352928146 428130218 36748014 669102980 807343033 75275361 272574535 970717500 115552397 686909921 117811922 75659968 200121766 242319875 117659923 552339939 231713042 138980919 216670528 817771853 606531537 597511165 277341124 571114746 201337432 797223275 931606462 658184890 92228879 343809962 143821183 819990703 973258451 599740793 903910160 764541393 484454772 433418665 233468074 245706349 597544504 483009951 557529915 885717154 29110358 575806421 107305192 976793827 465575292 512261208 770879365 167038584 137239626 576862539 315381535 827924988 256619221 910680931 493833331 857524192 674208549 337168490 835648884 356485351 689116599 116457917 320281032 768963752 177705467 701543118 536905036 186635792 610627799 39143330 148265612 729435613 941808930 194122067 395246412 124821283 201682474 647092367 122198786 680461259 952488495 531289111 300338520 224571663 549359333 261426497 334742191 868618240 794047478 339060855 425856151 457108480 348375934 680134070 189383256 603603272 519755405 660493072 860934509 456871267 764359593 467696938 48646660 430426033 161737033 839378367 689991039 344039909 228242011 530229275 281358069 134654088 499451582 776219552 390096817 604773236 522429385 538699844 800937906 379300441 434342083 185193233 177967658 508202299 979523944 878526116 552198144 788782834 568900202 12894127 319471694 108063144 574858222 813753720 455329507 192955231 353057803 11563607 476040385 960938601 155733839 815863356 520623776 607138286 650179385 813487398 272598378 648157801 756444864 436007341 952999613 581583403 563415754 54823801 759484268 957318615 436909750 51544520 854084606 925057252 199611091 942593516 229250349 66904095 741341414 835549643 782619753 408867878 987703464 592821342 640822867 48225261 926724678 153017394 196761410 31159101 472832223 814971370 880827329 408987952 280195338 756538042 600630031 307439799 354341709 215411438 37388189 380805908 337946279 285270113 123713428 453372512 296636679 18156806 462190925 573684742 277440466 635806563 984304086 63480646 683262049 212912913 432745844 463928243 35233920 1333565 336269339 229858229 427422449 949580074 58974200 734381320 669573095 605945517 322122728 564104507 543783819 789858992 224348670 514626099 236533883 558107567 943512577 126551205 750540870 972847678 171682795 569015967 332484081 260813696 953810027 78211583 486637173 802699697 727771492 757943034 80849726 32896158 213081196 216793751 352180397 787058216 822166350 104027954 859066008 33471685 873425544 842812154 251498181 451453951 240060878 37518450 280358258 719739123 749724805 275033331 380938192 387585234 848478793 395719465 782585987 163322723 45488999 90388370 650619940 341051263 332143971 636262147 362896319 882629524 543316340 339185442 208560981 409838115 623110915 747418348 500389467 235272771 623698480 971661105 269264954 945852443 996650573 181206803 685306573 797565291 583200864 511570571 23028966 921659396 373577125 477504740 66991816 576570955 134619658 461127486 932611758 211270074 19388082 938318092 555673411 325949791 508311667 473880726 698214441 801782876 725417048 609203064 588084850 224162917 18604063 487615777 484500266 920699973 800683195 498500437 497319371 674666073 323179731 114458796 125122246 490106643 874664770 370053905 408884225 646057848 88982933 441107011 846651732 769636771 702875280 995771991 856406795 8693568 204556457 530957364 962803815 645488657 621488267 665871893 644307485 154063469 975195029 520115723 919409877 428033468 708477529 633788537 381355948 992201468 593850141 640347798 285019314 94016831 547296861 184514286 347105645 63271467 203666759 851846113 76618581 96837240 223044157 813826595 965999190 563898486 100890455 998883642 801454417 735128708 596258014 225863684 513750170 269650842 667285458 392655150 186233467 683993024 567757413 486143421 128949168 807790741 488030334 673237385 323879402 183803337 491758136 828996541 22353484 424648610 622933088 168012121 558932977 39838075 325034234 427002288
482240100 843681857 659889084 463184106 184676902 809906933 613005969 752714371 819297579 339878700 123421207 491328970 653546845 606487954 332295202 319971427 226631448 56215138 539119671 67004614 621026732 714568176 215174161 596873406 143069151 688444703 349894176 632866282 225990760 955782123 530259461 638752319 665423477 199940065 358769944 912984708 401907750 891586722 554393826 458627796 490602255 819127396 382533539 688049440 338685114 483911280 100550861 592478635 258935587 389172645 54294918 709462924 743724858 408449780 227632427 542957871 696761700 463784930 568344520 855190228 242508283 902100745 29688992 827974415 170826697 625229975 521392299 943003974 961396881 996821197 187228435 633205302 490605447 574187137 358257078 661334127 913757650 993667484 194093991 810024659 526528785 736015773 631207341 395494171 336654291 115499541 264389315 232089170 781216797 259045161 167056534 811139928 74668009 895028755 724745738 638917984 770026401 210324897 209002422 980264050 961919144 250511029 718046819 282205674 244078033 251502787 552885648 615996151 856887270 500604502 270670833 490268445 373898274 902765963 796690412 849923763 116563127 646382227 982026266 325925222 506233674 953784886 627446220 174824628 741526898 41858123 861771140 136889970 439215932 509267009 627104631 377008967 362944426 949454234 913647634 1020206 284307247 19220074 372425842 874798584 79792180 945380316 738263786 118557128 112996759 818302125 128454529 982098325 627064615 37736367 165593713 830465963 899261993 873284168 747319978 5611562 775089110 772339440 887029324 443935110 673468378 456696759 146367793 802221829 256314071 978202812 281874785 808364868 445416160 587629751 200910235 596638387 107644926 888597872 993800659 220032020 101149871 417798213 553638318 382091008 313121890 369811624 679951623 103455330 980982780 745857183 812963438 243511033 999890518 177030979 395721124 473932250 876046524 717842241 284367905 673812205 851100527 789246812 896562574 709725035 801005092 323621609 90252363 528488038 27847812 132824145 271380458 321155393 769255594 599969682 45374898 761173556 426207656 537410751 417210141 501425865 628768770 411625595 519945818 517604450 529222704 793370754 287980748 793332912 54111521 86710305 357099400 390733373 406014643 888779961 917588443 151727332 410254396 230458432 353698242 849221715 283927300 887848383 310630001 956426384 129339080 689901525 376597709 478766705 153015865 681562418 421914097 987579426 309983611 119988509 952670125 84633507 824621735 749093359 82766082 536745800 275816521 355214230 244697255 390368311 93141986 251050003 707772807 589484269 540989031 830527484 556673857 201461178 319685312 312867067 31085735 380129600 103744586 151035468 951286847 627073784 741160790 582030147 729410757 494408621 451023783 253458884 66492327 468103166 531804920 763435209 858722184 842546912 316307316 961143008 313814717 259523610 721861180 605560490 266453459 181706440 297670629 727517533 860458503 114792409 753651959 505772867 814585804 338954897 351758447 848546873 978884425 432388871 958119997 27226673 736293592 940136616 595746247 835747760 322596233 903339698 80386148 669871697 531920285 143265466 996705250 363757888 677763851 88289063 926167297 720372671 411775486 573180340 522381302 747986340 771404628 492866034 817141481 496075225 450518305 107333059 74256503 865885915 179898666 135760353 946066992 212748092 62870891 832078933 409634074 344472610 784148113 589741824 194100268 8763333 88675969 640976917 97961684 540512244 394278607 425263261 719265138 179206801 409197896 84298994 864513499 903058960 277009513 136649028 309052886 799135740 971996645 895179287 65385378 908240755 240223522 589231299 866708591 831383973 44732860 247819251 728263904 139407448 906939905 480514086 542351759 428082279 887389044 117714481 705866121 907393598 535242059 650995132 610983630 594835040 724136177 653827008 560630482 600791522 598147716 801877775 769703679 528086765 936745304 349646540 801633073 714151231 642385010 830991599 330989112 85686955 508741901 264727234 680469594 636435860 889840921 681648486 543900110 513167222 230630839 946569807 695253313 351351134 134671294 878982596 761960533 416927852 490181689 98340192 484574238 412937304 10593511 652400788 960175011 359638507 204529338 436199202 434764387 354418049 959573592 397195171 383196877 834335118 470695069 579889667 673544902 814747926 766433559 901501440 957537319 745752114 353322121 121756590 958406973 520920210 414212969 849139701 766306632 900187638 511522401 395147025 207230204 157149364 753021649 811162898 405540610 755070518 810987339 245877850 234604664 192980856 27046934 476502561 296431981 813190542 776634285 549144820 365157734 141015068 189631293 58264370 848185820 899554780 398860586 234447246 561160892 377788188 105042314 753480080 935951589 906169917 546155176 512080916 206922413 802945589 397794179 810535369 239975517 266195214 20446284 582911922 536786096 200890469 665809644 877222825 726037848 928392172 188866939 428580567 548517753 920818664 68059850 530089534 381546028 684756403 617913050 872231727 140627710 23126587 313001315 298909140 713025646 317633665 369177678 654270375 914115186 854903836 804150331 202045945 204352243 706641331 526354172 604165740 182518860 133207430 659083800 291816313 826262479 1071590 784142153 108057324 65544768 519298489 91859198 563996770 553972824 321953015 984185562 186395090 55274819 218411823 72200243 684156929 773717282 595103235 195199636 869760268 61007242 388788135 144318011 251968226 562145796 861857638 327238300 288640456 649219211 566701597 491051740 184202451 932753425 665443518 33646166 576877169 905044218 142228687 98198298 698956001 38956446 218267368 87704169 981345974 604290251 242502457 388518714 31965528 997450818 795329025 381277369 506896258 57351990 573942808 205897922 856563141 116611792 466351462 497490538 766889732 25988269 976715625 488132727 479390966 343581534 829098420 986045411 578359976 232479974 730066538 252401757 390814456 975744832 845924551 901834439 434649883 407235799 902359447 64073657 480501015 218537228 753935293 345868797 438500426 824544948 19449006 803939601 346741217 641310871 13727475 945214888 105070946 744718834 871268011 678849065 949727011 443433718 991702534 848544558 889618128 853026119 800786891 317948423 561021417 86690941 268001747 815761205 358795329 706878630 789644683 575914223 667374208 231503042 739004534 9939360 380056738 836693830 246810793 927557222 738941558 87700122 688737102 130292117 508718625 660128155 476545825 963722546 960874648 218289177 703784182 378418553 756480553 740277082 439447089 407950680 339666163 750298262 971814732 386445041 726294889 596088696 11536981 664268316 533616850 147738787 387578733 901811426 389272012 324101163 521492298 782610435 195118789 111173656 786833846 743280497 603339393 655222503 436841485 224918739 497704599 180161032 601010627 995259395 969297396 240483425 588744412 526019472 966409558 248729289 490183794 411772221 114333137 319164046 637743923 442940032 314171214 795830256 989848545 993272580 293334279 739462819 720606160 307715367 67526669 632367185 366318442 104412285 102477762 342896918 284912302 818224203 694257247 221928962 543906221 602155533 300876655 90274203 779765005 320756208 322020434 415722584 284528262 321266520 966532795 248950055 911292263 50820956 676616499 622952424 141231377 194908485 378887060 442212335 43327355 262114579 274352014 14004358 823662509 131436536 116930853 275510120 545957445 365128922 810809649 241088328 745520117 127586005 618440156 246978632 518057474 68315575 549402920 74514562 816868039 465259651 77385575 779605635 189958192 703541743 906590657 589619146 550217792 810765541 534864561 564240718 564032395 717587205 795233928 632745461 90399164 308968226 140376041 760963358 888909329 391534017 124195915 965963032 407688154 57657757 412557435 870197160 149061885 971642918 360961815 755665543 366640757 780988412 963978515 366099938 722891470 774630777 616869432 597746905 312016555 479900453 756571552 538472448 948738369 409653823 840802364 80134624 762229977 791011131 86831950 282889591 980632401 724831806 53111023 73873076 812549276 11138468 976885386 338017532 738601789 282236027 734057823 749017000 408214736 900389637 190137601 739059333 996085890 482289466 221730264 939187794 300310420 436110660 333707680 940484421 468015580 820927489 798045672 313838983 327547971 970785668 351601300 477019571 212086088 925630867 964965468 531966811 64248699 533522475 323066699 68298627 328796675 494828536 643501376 528056612 643726617 2091742 923161200 848747946 254706315 339946099 882252770 808146295 951001658 768552066 300220402 96916062 241602716 731769737 325421262 380746792 756318010 572707643 219014396 455854866 481727283 917425920 755556306 580708429 130746296 516295280 336368637 789183613 653747854 65111516 16711163 240560699 108840591 869501637 838241440 714151059 688271913 268159586 624844181 356835207 249927645 362401311 121266644 437188746 872886465 83102233 304248366 41536773 517098239 757923746 638061509 414751445 736666196 907335107 470914706 234997451 100139153 830712245 749327328 246791979 560257054 72340839
